#ifndef CGRAPH_H
#define CGRAPH_H
#include <vector>
#include <limits>
#include <map>


using namespace std;

using Byte = unsigned char;

using VertexTag = char;
const VertexTag VERTEXMAX = std::numeric_limits<VertexTag>::max ();
const VertexTag VertexNull = std::numeric_limits<VertexTag>::min ();

using EdgeInfo = int;
const EdgeInfo EDGEINFO_NULL = std::numeric_limits<EdgeInfo>::min ();
const EdgeInfo EDGEINFO_MAX = std::numeric_limits<EdgeInfo>::max ();

enum MODE{
    WHITE = 0,
    GRAY,
    BLACK
};

struct VertexNode;

struct EdgeNode
{
    VertexNode *pNextVertex; //指向下一个该顶点的下一条边或弧
    EdgeNode(VertexNode *pNext)
    {
        pNextVertex = pNext;
    }
};

struct VertexNode
{
    VertexTag vTag; //顶点标识 0 ~ VERTEXMAX
    MODE status; //状态
    VertexTag PreTag; //前驱标识集
    int nLevel; //层级

    vector<EdgeNode *> Edge;//顶点边的集合

    VertexNode(VertexTag tag)
    {
        vTag = tag;
        status = WHITE;
        nLevel = -1;
        PreTag = VertexNull;
    }
    ~VertexNode()
    {
        //释放内存，但不会删除容器中的元素
        for(auto iter = Edge.begin ();iter != Edge.end (); ++iter)
            delete *iter;
    }
};

class EdgeElement;

class CGraph
{
private:
    int m_iCapacity;
    bool bVec;

    map<VertexTag, size_t> m_tagToIndex;

    vector<VertexNode *> m_vecVertexSet;
    vector<vector<EdgeInfo>> m_vecMatrix;

    void freeVertex();
    void init(int iCapacity);

    void DFS_VISIT(VertexTag tag);
    static int StopTag;

    vector<shared_ptr<EdgeElement> > getEdgeSet();
    bool IsVertexInPen (const vector<VertexTag> &vecVertexParent, shared_ptr<EdgeElement> pEdge);
    VertexTag FindParent(const vector<VertexTag> &vecVertexParent, VertexTag vTag);
public:
    CGraph(int iCapacity, bool bVec = true);
    ~CGraph();
    bool addVertex(VertexTag tag);
    void resetGraph(int iCapacity = -1);
    bool connectVertex(VertexTag tagA, VertexTag tagB, EdgeInfo info = 1);

    void printMatrix(const vector<vector<EdgeInfo> > *vecMatrix = nullptr);
    void printVertexInfo();
//    void printEdgeInfo();
    //广度优先遍历
    void BFS(VertexTag vTag);
    void BFS_(VertexTag vTag, int nLvl = 0);

    void LimitPath(VertexTag vTag1, VertexTag vTag2);
    void LimitPath_(VertexTag vTag1, VertexTag vTag2);

    //深度优先遍历
    void DFS();

    //最小生成树
    int Prim();
    int Kruskal();

    //最短路径
    void 人();
    void Floyd();
};

using INDEX_TO_PATH_INFO = std::pair<VertexTag, EdgeInfo> ;

class EdgeElementHelper
{
public:
    EdgeElementHelper(const EdgeElement &Elem):
        pEdgeElem(&Elem)
    {

    }

    const EdgeElement *pEdgeElem;
};

class EdgeElement
{
public:
    std::pair<VertexTag, VertexTag> VertexPair;
    EdgeInfo Cash;

    bool operator <(const EdgeElement &Elem)
    {
        return Cash < Elem.Cash;
    }

    bool operator ==(const EdgeElementHelper &Elem)
    {
        if( VertexPair.first == Elem.pEdgeElem->VertexPair.first
                &&  VertexPair.second == Elem.pEdgeElem->VertexPair.second
                && Cash ==  Elem.pEdgeElem->Cash)
            return true;

        return false;
    }

    pair<bool, bool> operator ==(const EdgeElement &Elem)
    {
        //表示完全相同
        if(*this == EdgeElementHelper(Elem))
            return make_pair(true, true);

        //表示相同，但是反向相同
        if( VertexPair.second == Elem.VertexPair.first
                &&  VertexPair.first == Elem.VertexPair.second
                && Cash ==  Elem.Cash)
            return make_pair(true, false);

        //表示完全不同
        return make_pair(false, false);
    }
};


#endif // CGRAPH_H
